package exercises.newcoder.solution;

import java.util.HashMap;

/**
 * <a href="https://www.nowcoder.com/practice/bfc691e0100441cdb8ec153f32540be2?tpId=202&&tqId=38712&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC3 多少个点位于同一直线</a>
 *
 * @author or2
 * @Description 对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上
 * @create 2021年09月12日 时间: 16:59
 */
public class MaxPoints {
    public static class Point {
        int x;
        int y;
    }

    /**
     * @param points Point类一维数组
     * @return int整型
     */
    public int maxPoints(Point[] points) {
        if (points.length < 3) {
            return points.length;
        }
        int ans = 0;

        for (int i = 0; i < points.length; i++) {
//            该斜率下 点的个数
            HashMap<Double, Integer> countSlope = new HashMap<>();
//            与 point[i] 相同的 点的个数
            int repeat = 0;
//            point[i] 有关直线含点的最大值
            int iMax = 0;
            for (int j = i + 1; j < points.length; j++) {
                int dev = points[j].x - points[i].x;
                double weightSub = (points[j].y - points[i].y);
                double slope;
                if (dev == 0) {
//                    去重 - (有重复点, 但是按提议不需要去重)
                    if (weightSub == 0) {
                        repeat++;
                    }
                    slope = Integer.MAX_VALUE;
                } else {
                    slope = weightSub / dev;
//                    小心浮点数的 -0
                    if (slope == -0) {
                        slope = 0;
                    }
                }
                int keyVal = countSlope.getOrDefault(slope, 1) + 1;
                countSlope.put(slope, keyVal);

                if (keyVal > iMax) {
                    iMax = keyVal;
                }
            }

            int curAns = iMax + repeat;
            if (curAns > ans) {
                ans = curAns;
            }
        }

        return ans;
    }
}
